# 划分字母区间： 

"""
直接模拟分析这个过程，然后当前字符没有在 map里出现过，说明前面没有该字符， 他可能作为新的一段，那么添加到 栈中。 当后面出现的字符 和前面的字符重复时， 那么重复字符之间的，都不是 一段的末尾元素了，弹出栈。
需要记录每个元素的 初次出现的下标~ 表达能力有些差，总的讲，大家模拟一下这个过程。 map存储的是遍历过的元素和 第一次出现时的下标。 栈存储的是， 每一段的末尾元素下标。当再遍历元素和前面元素重复是， 
栈中的有些元素，必然不能在当做 段为尾，就需要出栈，当前元素作为新的 段尾。
"""

# 自己的想法
class Solution:
    def partitionLabels(self, s: str) -> list:
        """
            看到这题一分析，直接模拟思路。我首先想到的是栈和hashmap
            栈是用来存放那些片段的分割下标， hashmap 是用来判断，下一元素是否在 前面出现,并记录元素第一次出现的位置（下标）
        """
        n = len(s)
        charMap = dict()
        snippetStack = [-1]
        # 循环遍历每个元素
        for i in range(n):
            # 1. 如果之前没出现过，那它自己可能是一个段（只有一个元素那既是段头，也是段尾），加入到栈中，并加入到 字典中
            if s[i] not in charMap:
                snippetStack.append(i)
                charMap[s[i]] = i
            # 2. 当前元素和遍历过得元素重复，那它将是新的段尾， 要去除栈中不能做段尾的
            else:
                # 假如 abca  [a, b, c] 都入栈，没重复能做单独的段， 但是 遍历到最后的 a, 在a 第一次出现到 
                # 当前位置的元素都不能最为段尾，当前元素入栈作为新段尾，其中的出栈
                while snippetStack and snippetStack[-1] >= charMap.get(s[i]):
                    snippetStack.pop()
                snippetStack.append(i)

        # 返回结果
        return [snippetStack[i] - snippetStack[i-1] for i in range(1, len(snippetStack))]



class Solution:
    def partitionLabels(self, s: str) -> list:
        """
            看到这题一分析，直接模拟思路。我首先想到的是栈和hashmap
            栈是用来存放那些片段的分割下标， hashmap 是用来判断，下一元素是否在 前面出现,并记录元素第一次出现的位置（下标）
        """
        # 计算长度，定义栈，字典
        n, charMap, snippetStack = len(s), dict(), [-1]
         
        for i in range(n):
            if s[i] not in charMap: charMap[s[i]] = i
            while snippetStack and snippetStack[-1] >= charMap.get(s[i]): snippetStack.pop()
            snippetStack.append(i)

        # 返回结果
        return [snippetStack[i] - snippetStack[i-1] for i in range(1, len(snippetStack))]




# 第二种思路

class Solution:
    def partitionLabels(self, s: str) -> list:
        """
            还一种思路，计算每个元素，出现的最远的位置。 比方说 defegde ， d -> d 中最远能到的是 defegde，那它就是最小分一起的片段
        """
        # 1. 计算每个元素最远出现的位置
        charFurthestIndex = [0] * 26
        for i, c in enumerate(s):
            charFurthestIndex[ord(c) - ord("a")] = i
        
        # 2. 找出所有段
        i = 0
        rst = []
        while i < len(s):
            start = i
            end = charFurthestIndex[ord(s[i]) - ord("a")]
            maxIndex = 0
            while i <= end:
                maxIndex = max(maxIndex, charFurthestIndex[ord(s[i]) - ord("a")])        
                i += 1
            while i <= maxIndex:
                maxIndex = max(maxIndex, charFurthestIndex[ord(s[i]) - ord("a")])        
                i += 1
                
            # i定位到下一段的开始
            i = maxIndex + 1
            rst.append(maxIndex - start + 1)

        return rst



# 优化后的代码
class Solution:
    def partitionLabels(self, s: str) -> list:
        """
            还一种思路，计算每个元素，出现的最远的位置。 比方说 defegde ， d -> d 中最远能到的是 defegde，那它就是最小分一起的片段
        """
        # 1. 计算每个元素最远出现的位置
        charFurthestIndex = [0] * 26
        for i, c in enumerate(s):
            charFurthestIndex[ord(c) - ord("a")] = i
        
        # 2. 找出所有段
        i = 0
        rst = []
        while i < len(s):
            start = i
            maxIndex = charFurthestIndex[ord(s[i]) - ord("a")]
            
            # 要注意这一点， maxIndex 是不断更新的，因为当前默认为 第一个元素的最后出现下标为 maxIndex，其中遍历其他元素时，
            # 可能有更远的，所以要一直找最远的。然后 才是一段！
            while i <= maxIndex:
                maxIndex = max(maxIndex, charFurthestIndex[ord(s[i]) - ord("a")])        
                i += 1

            rst.append(maxIndex - start + 1)

        return rst


# 这里用了两层 while 但是复杂度还是O(n), 其实还有更直观的一层 for循环写法

